perm filename CACHE.415[AM,DBL] blob
sn#435190 filedate 1979-04-15 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \input paper.tex
C00005 00003 \NSECP{INTRODUCTION}
C00021 00004 \NSECP{THE ASSUMPTIONS}
C00043 00005 \NSECP{SELF-MODIFICATION & -MONITORING: INTELLIGENT LEARNING}
C00080 00006 \NSECP{CACHING: INTELLIGENT REDUNDANCY}
C00110 00007 \NSECP{EXPECTATION-SIMPLIFIED PROCESSING: INTELLIGENT FOCUS OF ATTENTION}
C00121 00008 \NSECP{LEVELS OF ABSTRACTION: INTELLIGENT KNOWLEDGE STRUCTURING}
C00143 00009 \NSECP{COGNITIVE ECONOMY REVISITED}
C00145 00010 \NNSECP{Acknowledgements}
C00146 ENDMK
C⊗;
\input paper.tex
\TITL{COGNITIVE ECONOMY}
\vskip 20pt
\ctrline{\:=in Artificial Intelligence Systems}
\vfill
\AUTHO{Douglas B. Lenat, \ Stanford University}
\AUTHO{Frederick Hayes-Roth, \ Rand Corporation}
\AUTHO{Philip Klahr, \ Rand Corporation}
\vfill
\vskip 10pt plus 2pt
\NNSECP{ABSTRACT}
Intelligent systems can explore only tiny subsets of their potential
external and conceptual worlds. To increase their effective
capacities, they must develop efficient forms of representation,
access, and operation. Abstraction, caching, and
expectation-simplified processing are principal examples of such
capabilities. These capabilities in turn can combine to produce
significant increases in performance. For example, all three can
combine to simplify process simulations and, consequently, those
functions that exploit simulations, such as interpretation,
detection of surprising events, and planning. In this paper we
develop several economic principles for modern AI systems. Our
analysis leads to some counterintuitive ideas and proposed
policies which are not generally followed because their contribution
to overall cognitive utility is not readily apparent. For example,
we challenge the typical practice of storing properties "economically"
in hierarchical inheritance nets. This non-redundant storage practice
provides minimal storage cost savings, but significantly increases
may processing costs. As an alternative, we suggest storage schemes
to improve performance by exploiting various forms of redundancy
consistent with general caching heuristics.
\vfill
\eject
\NSECP{INTRODUCTION}
When we build an AI program, we often find ourselves caught in the following
tradeoff: On the one hand, we want to develop our initial systems quickly
and painlessly, since they are experimental and ephemeral. On the other hand,
we want our systems to run as efficiently as possible, to minimize the
temporal delays and to reduce the cpu time and space required.
We are torn between
{/it expressibility} and {/it efficiency}.
Many AI researchers {/sl cum} language designers have focused on {\it
expressibility}, the problem of rapidly constructing a working
experimental vehicle.\foo{This objective is apparent in the goals {\:c SAFE}
[Balzer 77].
{\:c PSI} [Green 77], {\:c EMYCIN} [ref], {\:c RITA} [ref] {\:c ROSIE} [ref],
and
{\:c KRL} [Winograd & Bobrow 77].}
They have produced some excellent software such as
Interlisp's {\:c DWIM}, File, and Break packages.\foo{[Bobrow & Raphael 73] is
still an excellent discussion of the issues involved in such ``AI language"
efforts.}
Four fundamental techniques
utilized in highly {\it expressive} programs are:
({\it i}) reliance upon a very-high-level language,
({\it ii}) planning and reasoning at multiple levels of abstraction,
({\it iii}) inference by pattern-directed knowledge sources.
({\it iv}) minimal, nonredundant representation, as in a canonical
generalization/specialization hierarchy.
This paper addresses the second goal of AI programming,
{\it efficiency}.
We present techniques which do not sacrifice expressibility, yet enable
programs to (semi-)automatically improve themselves and thus, increase
their productivity.
The basic source of power is the ability to predict the way that the program will
be used in the future, and to tailor the program to expedite such uses.\foo{This
approach is sometimes used {\it manually}, as when a program is quickly coded
in an expressive but inefficient form, used heavily, and then recoded in a
much more optimized form. Thus, e.g., Ray Carhart spent 1977
rewriting CONGEN, the central module in Dendral, for a minicomputer.}
The traditional approach to program optimization has assumed that the
programmer characterizes the predicted program behavior (e.g., by explicitly
providing assertions) or that static analysis can identify significant
optimization opportunities. Three types of methods for analyzing program
descriptions in this way include:
({/it i}) analyzing
program flow and structure [refs Knuth, Dijkstra],
({/it ii}) designing data structures to be appropriate,
and ({\it iii}) compiling (as in the {\:c FORTRAN H} compiler; optimizing
transformations of the program [Burstall & Darlington 73], etc.)
We advocate the use of methods more {\it dynamic} than these. Rather than
improving the static description of a program, we propose
to modify the program structure to adapt it to its
operationa environment.
One valuable source of prediction comes from the program's experiences as it is run.
If a program can ``learn" from its experiences, it might try applying each piece of
newly acquired knowledge to the task of specializing itself, modifying itself
to run more efficiently in the current runtime environment.
We believe that a program's ``intelligence" can be increased in this way;
that is, by increasing its ability to
acquire appropriate knowledge, to organize that knowledge, and to refine
the conditions under which that knowledge is recognized to be applicable.
There's a limit to the size of programs we can successfully implement,
and this might be overcome by programs which are self-extending, which actively
do things to enlarge their input domain, their capabilities.
Some earlier automatic programming systems [Darlington & Burstall, Lenat's PUP6,
Jim Low, Kant & Barstow]
were designed to improve programs' efficiency, and many of their
delete others?]
ideas have found their way into the techniques we now describe.
Those systems
had program construction, transformation, and optimization as their primary
task; we are proposing general methods to provide
self-improving abilities
to other kinds of AI programs
(understanders, theory formers, expert simulators, planers, etc....)
Three ``dynamic'' abilities which make a program {\it efficient} are:
\noindent $\bullet $
{\bf Dynamic self-monitoring} (the ability to sense, record, and analyze
dynamic usage) {\bf and self-modification} (the ability to use that
knowledge to redesign/recompile itself with more appropriate
representations, algorithms, data structures; i.e., intelligent learning.)
\noindent $\bullet $
{\bf Caching of computed results}
(storing the results of frequently-requested
searches, so they needn't be repeated over and over again; i.e.,
intelligent redundancy.)
\noindent $\bullet $
{\bf Expectation-filtering}
(using predictions to filter away expected, unsurprising data,
thereby freeing up processing time for more productive subtasks;
i.e., intelligent focus of attention.)
A fourth ability, which we shall also discuss in this paper, is one of the
more static techniques mentioned earlier, a kind of ``designing appropriate
data structures":
\noindent $\bullet $
{\bf Multiple levels of abstraction}
(redundant representation of knowledge at several levels of abstraction
can be an economical way of structuring a knowledge base, especially if the
program's tasks are large and the resources available for different tasks
vary widely in magnitude;
i.e., this is a technique for intelligent knowledge organization.)
\yskip
{\it Cognitive economy} is the term by which we describe such heightened
productivity.
Computer programs, no less than biological creatures, must perform
in an environment: an externally imposed set of demands, pressures,
opportunities, regularities.\foo{For a similar recognition of the
importance of the ``task
environment'', see [ref to Newell & Simon's HPS].}
Extending this analogy, we find that
cognitive economy is the degree to which a program is adapted to its
environment, the extent to which
its internal capabilities (structures and processes) accurately
and efficiently reflect
its environmental niche.
\hbox par 2.9in{ % this makes a space for the little figure; see below.
Notice that representing a corpus of knowledge as a minimal
(canonical) generalization/specialization hierarchy, with
interpretatively-computed inheritance, is {\it not} cognitively economical:
this technique
favors expressibility, compaction of representation, at the expense of
performance. It is true that a dog is a mammal, and a mammal is an
animal, and from those two we could compute that a dog is an animal (see
Fig. n), but it is more cognitively economical to store one redundant arc
than to recompute it frequently. Psychological studies
[Hayes-Roth & Hayes-Roth, 1974; Rips, Shoben, & Smith,
1975] indicate
just such redundancies being created and strengthened by repetitions.
}
[[in space above, insert DIAGRAM OF DOG/MAMMAL/ANIMAL,
WITH REDUNDANT ARC AS A !STRONG! DOTTED ARROW]]
Obviously, the economy of specific representations and related inference
methods depends heavily on underlying machine architectures and costs. We
assume that intelligent systems aim chiefly to produce useful results
(e.g., novel hypotheses) as raidly as possible. In sort, they should
search cleverly and fast. Thus, {\sl a priori} notions of aesthetics or design
economy have little bearing on cognitive economy. Massive redundancies
in storage, processors, and inference processes seem more directly
relevant. Furthermore, we suppose that, like people, intelligent software
should eliminate slow, interpretive searches for previously solved
problems (especially if the same problems are repeated often.)
To this end, cognitive economy may be achieved
through dynamic compilation of action sequences. Such compiling would
reduce the time-cost to effect the corresponding behavior; on the other
hand, this efficiency would be gained at the cost of interpretability,
interruptibility, and modifiability. These are desirable attributes where
a program potentially needs continual changing.
In typical situations, both efficiency
of compiled forms and accessibility to declarative forms are intermittently
needed. These different needs point again to the economic benefits of
mantaining simultaneously alternative and redundant representations.
Every scientific theory is constructed in a rich context of surrounding
theories, methods, and standards determining which experiments are
reasonable ones to perform and which point of view to take when interpreting
the results -- in short, a {/it paradigm}. We feel it useful
to articulate the ``core" of our paradigm (the assumptions our theory
rests upon) before delving into more detail about cognitive economy.
For that reason, the entire next section is devoted to a presentation of our
assumptions, including:
a model for intelligence
(Section 2.1), a model for how intelligent computer programs may be
organized (Section 2.2), and a model of the characteristics of present
computing engines (Section 2.3).
Section 3 assumes these models, and contains detailed discussions and
examples of the three main components of cognitive economy:
dynamic self-monitoring and self-modification (Section 3.1),
caching of computed results (Section 3.2),
and expectation-filtering (Section 3.3).
One interesting result that emerges is the prediction that as task size
grows large enough, the same techniques that currently support expressiveness
(e.g., multiple levels of abstraction) will become important for efficiency
-- for cognitive economy -- as well.
\NSECP{THE ASSUMPTIONS}
Our theories are erected upon a foundation of assumptions, including:
(i) We continually face searches in more or less immense spaces;
intelligence is the ability to bring {/it appropriate} knowledge to bear,
to speed up such searching. Increasing intelligence then comprises
increasing knowledge, improving its organization, and refining the
conditions for its
applicability. How are these new discoveries made? Empirical induction
(generalizing from experimental and other observations), analogy, and the
criticism of existing theory all lead to new conjectures, new
possibilities.
(ii) Intelligent systems can make the applicability of their knowledge
explicit by representing that knowledge as condition-action rules (If {/sl
situation} then {/sl appropriate reaction}). Such pattern-directed
inference systems (PDIS) can benefit from a schema representation (frame,
unit, being, script, etc.), because this adds structure which the rule
descriptions can exploit.
(iii) Current computing technology presents us with limited cycles, cheap storage,
and expensive knowledge acquisition.
While the reader may wish to turn immediately to a discussion of our
detailed ideas on cognitive economy (Section 3), it is useful to examine the
above assumptions in more detail first.
\SSEC{A Model of Intelligence}
Many human cognitive activities, including most of those commonly referred
to as ``requiring intelligence," can be cast as searches, as explorations
through a search space, meandering toward some goal. We call a
problem-solver more intelligent if it can work efficiently toward a
solution even in the face of an immense search space and an ill-defined
goal. Somehow, it is imposing more structure on the problem, and using
that to search more effectively. How might it do this?
According to our model of human intelligence, it accomplishes the task by
bringing knowledge to bear, knowledge not supplied explicitly in the
problem statement. This knowledge can be about problem-solving in general
(e.g., how to recognize and break cultural blocks [refs to Conceptual
blockbusting] or about the problem
domain specifically (e.g., which groups of atoms can usually be treated as
superatoms). This knowledge may have been learned long ago or generated
more recently during an
early phase of work on the current problem.
This implies that a problem solver can become more effective by (i)
increasing his knowledge, (ii) better organizing his knowledge, and (iii)
refining his criteria for deciding when various pieces of knowledge are
applicable. In terms of production (If-Then) rules, these correspond to
adding new rules, modifying the data structure in which rules are held,
and modifying the conditions (If parts) of existing rules.
One very basic assumption we are making is that of {\it continuity}:
the problem-solving environment does not change its character too
radically, too rapidly.
If the program abstracts from its experiences a plausible heuristic H, it may be
able to analyze past scenarios to verify that possessing and obeying H
would definitely have improved its performance (e.g., led to the current
state of knowledge quicker);
but its only justification for believing that H will help it in the {\it
future} is the empirical evidence for the continuity of the environment.
Learning can be translated into action only if the structure of the domain
remains consistent, similar to the earlier situations that motivated the
learning.
A related assumption is that of {\it irreversible knowledge accretion}.
Our body of facts and observations continually grows and only occasionally
shrinks. Certainly the abandonment of a whole system of thought is a
rare event indeed (ask Kuhn!),
whereas the adoption of new systems of thought is part of
the standard educational process.
How is new knowledge discovered? One route is that of {/it abstraction}:
condensing many experiences into a heuristic which, in hindsight, we see
would have greatly aided us in the past, which would have speeded up our
reaching this state in the search. Closely related is {/it
generalization}, often merely expanding the domain of relevance of a
specific bit of knowledge we already possess. {/it Analogy} is one of
the most useful techniques; one can draw parallels not merely to other
existing facts and heuristics, but also to the {/sl paths} which led to
their discovery (e.g., even if a result in organic chemistry does not map
over into the inorganic world, the experiment which led you to that first
fact may map over into an experiment which {/it will} reveal a useful fact
in inorganic chemistry; even though the analogue of a mathematicl theorem
may be false in some new domain, the analogous proof technique may be
useful). Another path to discovery is {/it specialization} of more general
knowledge. Finally, we mention the process of {/it hypothesization,
criticism, and hypothesis refinement}, which is a common and powerful method
of spiralling in toward precision. In mathematics [Lakatos] and many
scientific disciplines [Musgrave & Lakatos], counterexamples to current
theories arise frequently, and their incorporation often demands a
deepening of the theory, an increase in knowledge [Hayes-Roth,
Klahr, Burge, & Mostow, 1978].
Experiments such as the AM program [ref] support our assertion that these
methods can adequately guide even open-ended searches for new definitions
and conjectures. But how can an intelligent system be programmed, how can
such systems be organized?
\SSEC{A Model of Intelligent Program Organization}
[[Most of this can go away vis a vis the IJCAI audience]]
Since we want our AI programs to access, reason about, and expand their own knowledge
bases, it is useful to represent such knowledge in a clean, modular form
(e.g., any one of the current schematized representations.)
The preceding remarks about intelligent problem solving apply equally to
``hardware" and ``wetware" alike. To be intelligent computer programs
must ultimately grapple with the tasks of knowledge acquisition,
representation, and refinement. We cannot provide an absolute answer to how
they should be organized, but we can posit some design constraints which
have proven useful so far.
A very general heuristic in AI programming is the following: If your
program is going to modify its own {\bf X}, then make {\bf X} as
separable, clean, and explicit as possible. In our case, {\bf X} can be
instantiated as ``knowledge", or as ``applicability conditions for each
piece of knowledge." In this case, the heuristic advises us to represent our
knowledge in a separate, clean, explicit form, say as knowledge modules
having some fixed structure, and also advises us to keep the applicability
conditions for each knowledge module separate from the rest of the
knowledge it contains.
This naturally leads us to a pattern-directed inference system, in which
knowledge is broken into separate modules, each with an explicit set of
relevancy tests [Waterman & Hayes-Roth, 1978]. Such systems arising in
Pittsburgh may champion
syntactic purity, while those arising in
California may tend toward the baroque,
but such variations should not obscure their common source of
power. The dominant PDIS architecture has knowledge broken into a set of
condition-action productions, rules of the form IF {/sl triggering
situation} THEN {/sl appropriate reaction}.
Having a clean representation for rules means having a clean, precise,
elegant language in which to express them. By structuring the conceptual
knowledge of the system, by partitioning each module's knowledge into
several categories, a rule can condense an entire cumbersome description
into a simple reference (e.g., a pointer). The popular schematized
representations of
knowledge (scripts for episodes, frames for static situations, beings for
specialists, units for everything) enable a rule like ``If there are no
known methods specific to finding new examples of prime numbers, Then..."
to have its condition coded as a simple null-test on the ``To-get" subslot of
the ``Examples" slot of the schema for Prime Numbers. By a judicious choice
of slot types and subslot types, the system builder can reduce most
triggering conditions to such quick checks on the state of various
(subslots of) slots of schemata.
Additional knowledge is required to locate efficiently all the rules which
{/it might} have their conditions satisfied in a given situation, and also
to decide which rules to execute (obey) among those whose IF parts
have triggered (been satisfied).
Special organizations can expedite the detection of potentially relevant
rules.
For example, AM[ref] organized
mathematical concepts into a generalization/specialization hierarchy and
tied each rule to its most relevant concept. To find rules potentially
relevant to concept C, AM could look first at the rules tacked
onto C, the at those associated with C's generalizations,
{\it their} generalizations, and so on. By
inheritability, any rule relevant to judging Objects in general was
(potentially) relevant to judging an Abelian group; any technique for
estimating the value of any function was relevant to estimating the value
of Ackerman's function; etc.
Controlling such searches requires an explicit focusing of attention, a selection of a ``current
topic" C from which the above rippling proceeds. We favor the maintenance
of a separate data structure for this purpose, an agenda of topics to
consider, of subtasks to work on [Hayes-Roth & Lesser, 1977; AM].\foo{
The intrinsic utility of agendas can be abstracted from the current
incarnations. Namely, the policy of
responding first to those things that seem most important, that demand attention,
and for which ignoring them might lead to worse consquences than ignoring
any of the competing alternatives.}
Knowledge may be brought to bear to
select a topic, then the above quest for potentially relevant rules is
carried out, then they are examined to find the truly relevant satisfied
set, and finally some subset of those are fired off.
The half-frame problem
In which the reasons supporting the tasks have the form ``stiuation X is
not yet attained, but executing me will help you get there"
(e.g., facet f of concept C has only 2 entries)
Then at task-choosing time, if a task's reasons are out-of-date, it is
most likely that that is because some of them are no longer valid,
hence that the rating of the task will DECREASE
So, all we need do is re-evaluate the top task, get a new LOWER number
for its priority, reinsert it into the agenda, etc., and continue
until the top task remains at the top. The half-frame problem
gets its name from he fact that we do have to reevaluate some
tasks to see how the world has changed out from under them, BUT
in general we need only do this for a small number of tasks to find
the best one, not for ALL the tasks.
Another approach to locating relevant rules by a kind of focus of attention
has been described within a question-answering paradigm [Klahr PDIS]. Deductive
interactions among the rules are compiled into a separate graph which is used
to quickly find deductive chains through the rules. The chains are turned into
proof plans which epresent a set of potentially relevant rules needed to prform
a desired deduction. Subsequent processing phases solve subgoals and validate
the entire proof.
\SSEC{A Model of (Present) Computers}
Since we are considering the problem of building computer models of
intelligent behavior, many of our assumptions deal with the
characteristics of present-day computers. They are the symbol manipulators
we use, but were not designed for that general purpose.
The foremost quality of computing machines, as we know them today, is their
limited ``inferential bandwidth." Although they provide virtually {/sl (sic)}
limitless storage capacity, these machines can process only a small fraction
of this information in a reasonable amount of time. Two primary reasons
for this disparity between storage and generation capacities include:
(1) knowledge acquisition proceeds slowly and expensively; and (2) inference
processes depend on operations that ordinarily require cycles of
uniprocessor systems. The first problem places a cultural limitation on the
development of intelligent machines. This development is restrained by our
inability to express what we would like our machines to do or to convert
these expressions into effective machine interpretable codes. The second
problem reflects a technological constriction of our potential. The
so-called vonNeumann bottleneck, caused by machine architectures that
sequentially interpret program steps through a single logical processor,
strongly motivates concern for programs that can minimize unnecessary
computations. In sme future environment, perhaps neither of these problems
will persist. In the meantime, however, we assume that two of the best ways
to increase AI system productivity, derived from these current limitations,
will be to expedite knowledge acquisition and to avoid unnecessary computing
(for instance, by opting to"store" rather than ``compute").
\NSECP{SELF-MODIFICATION & -MONITORING: INTELLIGENT LEARNING}
% was: \NSECP{SELF-MONITORING & MODIFICATION: INTELLIGENT LEARNING}
[[we will now first discuss how to use gathered knowledge,
and THEN talk about how to gather it dynamically.
First, add 1 para. summarizing the whole section.]]
\SSEC{DYNAMICALLY MONITORING THE TASK ENVIRONMENT}
Rather than working on a problem continuously, it may be better to expend some
time {\it learning} about the specific problem, its broader domain, or
problem-solving in
general. Note this suggestion would encompass traditional education (being
told), empirical research (observing),
and theoretical exploration (predicting).
While such ``very high-level" problem-solving strategies typify human
problemsolvers (especially those of us who have
rationalized spending twenty or more years ``in school''), very few programs to date
have employed any of these forms of learning to improve their operation.
Some programs (and wish-lists for program capabilities) have included learning
more about the problem being worked on;\foo{ McCarthy's advice-taker and
Balzer's dialogue system (to get airline reservation programs written) would
be told, Gelernter's theorem-prover (employing diagrams as analogic
models) could observe, Lenat's AM
could observe and predict.}
in this paper, however, we are stressing learning about the
ways the program is being currently employed.
\yskip
\noindent {\bf1. Learning by being told.} \
There are many situations in which a user could provide advice to a program.
{\it (a). } Some such advice would be task-specific: ``Integration by
parts won't work on this problem''; ``This is a very hard
problem''. This can easily be input as part of the user's statement of the
problem for the system to work on; e.g., the user might designate some methods
as being preferred or constrained, he might estimate a resource allotment, etc.
{\it (b). } Another type of advice
will apply permanently to the nature of the program's functioning
(e.g., ``Answers, even if uncertain, must be produced in real time'';
``Hard problems will be
starred''). Such knowledge can be reflected permanently in
the design of the program, in its code.
{\it (c). } But there is an intermediate level of advice, some information
the user knows will concern
the next several tasks to be submitted -- not just the present one and not
all future ones:
``The next four problems will be supplied in order of
expected difficulty"; ``Several of these problems share common assumptions
and raise related issues"; ``The user for the next entire
session will be a physician"; ``Until I find out why F34 returned NIL, I'll
be in debugging mode, not production mode". Such advice is rarely communicable
even to AI programs.
We believe this type of intermediate-level
advice would improve
programs if they had the opportunity to accept and use it.
In general, we would like to advise the program which capabilities to
consider and which to ignore during a prolonged period of solving closely
related problems.
A fixed (static) approach, for example, would be to define a few modes
(e.g., Debug, Demo, Production, Input,...) and permanently build into the code
all changes required to specialize the system for each mode. A flexible
(dynamic) approach would
provide a larger language in which the user could describe his current
mode of usage of the program (e.g., ``USAGE of KNOWLEDGE-BASE
will-be INCREASED VERY-MUCH'').
The program would translate such statements into
changes in its data structures, algorithms, explanations, core management
strategies, etc. In the preceding example, heavy usage of the knowledge
base might
cause the program to swap out its compiler, optimizers, and other code,
enabling it to hold many more knowledge chunks at a time in core.
The ability to hold more knowledge in memory would directly affect the rate
and probability of productive inferences. Similar effects have been shown
for humans [B. Hayes-Roth, 1979 Cognitive Science, in press]
\yskip
\noindent {\bf2. Learning by observing.} \
Spending a little time/space reconfiguring to reflect the current state
of the world (the nature of the recent and succeeding inputs) seems
worthwhile; the problem is how to know what that abnormal nature of the
environment is. In the last paragraph, we discussed the case where the
user explicitly tells the program. But this is often impossible (as when
the
user is unaware of an impending irregularity, or when the ``user'' is
nature), and almost
always a nuisance (learning the language in which to express such advice,
remembering to do it, taking the time to do it).
The next step seems to be to allow the program to {\it infer} such facts
about its run-time environment from observations.
What kinds of self-monitoring can be usefully employed?
The method which comes to mind first, perhaps, is to save a complete
record of everything that ever happened to this program: all the inputs
it received (when, from whom), function calls and accesses it made internally,
paths it chose/rejected (and why),
and outputs it generated. The program could in principle
deduce, from such an exhaustive
history-list, patterns such as ``very light usage of
compiler''; ``SQRT is always called
on the result of SUM-OF-SQUARES''.
The space costs of such an archive, and the temporal cost of the
procedures
to infer useful patterns, are surely prohibitive.
The more economical approach is to analyze in advance certain
features we would wish to look for in a complete history record, and then
to have the program record just enough dynamically to gather and maintain
those features. Some of these will be domain-independent and
commonly useful:
Frequency of calls on various functions, requests for subtasks, etc.;
Patterns in the arguments to calls on certain functions and inputs to the program;
Patterns in the sequence of calls on functions;
Patterns in functions' results (e.g., F34 always seems to
return a User-Name).
Some of the features will be domain-dependent specializations of the
preceding features (``Average degree of input equation'' is a special
``pattern in the input.'')
\yskip
\noindent {\bf Learning by predicting.} \
The theoretician and the engineer share
a powerful technique: manipulating
a model of a system to generate predictions and identify those possible
outcomes that would be desirable.
This is a third route to learning.
How might programs produce it?
What sorts of theories, or models, can be employed to generate new
information?
{\it Models of the program's users} can be valuable. This includes
maintaining and extending profiles of individual users and whole
groups. When a user opens a dialogue with Eurisko [ref] with the word
``Let", it is a safe bet that he's a mathematician. Later, when he
uses the word ``function," his membership in that group makes it easy
to determine which meaning he has in mind
(instead of, say, what a physiologist or a computer scientist might mean
by ``function.'')
When the program wishes to
mention the square-root of -1, it uses its Mathematician model to
choose an appropriate notation ({\it i} instead of, say, {\it j} for
engineers). Models can be arranged in a hierarchy, with inheritance
of features from more general groups to their subsets, a lattice
ultimately terminating in models of individuals. User inputs would
be recognized by various models, which would then hypothesize membership
in that group (or explicate some future conditions which would confirm or
deny such inclusion). Once triggered in this way, the user's apparent groups
(and its generalizations) would actively
filter his inputs and outputs, could modulate the program's actions (e.g., by
changing the worth of the ``Proof" concept, which in turn would change
the priority rating of tasks on an AM-like agenda and thus alter
the program's choice of what to work on next.)
New user models can be created either top-down (e.g., when a model has
many diverse instances or when it's proven historically to be very valuable,
try to split
it into several specializations, each having a share of the general model's
instances) or bottom-up (i.e., notice that a group of individuals share a
set of common characteristics, and create a new user group out of them).
The preceding kind of prediction is based on a theory of user types, embodied
in a set of ``typical representative'' models. The same source of power can
be used in many ways: stereotyping of events (i.e., scripts), stereotyping
of static complexes (i.e., frames), stereotyping of communities (i.e.,
actors, beings, contract nets). In all these cases, the source of power
lies in quickly recognizing probable membership in (applicability of) some
schema, after which all the rest of the schema
(plus knowledge about all its generalizations) is presumed to be relevant.
Programs might build up and utilize scenarios of how problems are solved
typically in their domain. The building-up could be top-down via specialization
or bottom-up via generalization, or even ``sideways" via analogy. The
models would be used for prediction (recognize relevant models and activate
them, have them hypothesize probable future situations).
Together, the models would form a theory of how problems are
solved in that domain.
\SSEC{DYNAMICALLY MODIFYING ITSELF}
SUMMARY: using knowledge of pgmming, task domain, and observations of the
actual runtime environment.
Tasks can be specified anywhere from a pure ``What'' (desired
input/output behavior) to a pure ``How'' (precise algorithms, data structures,
representations, formats). It has been observed [Feigenbaum ref] that one
of the goals of AI research is to push our ability from the How end toward
the What end of that spectrum. This often takes the form of designing a new
higher-level language than any that hitherto existed, one which takes over
more of the program implementation. We can see this as far back as
assemblers replacing machine language, and as recently as KRL and the
Molgen Units Package which extend Interlisp.
Assuming, then, that the user
desires merely to specify What, an intelligent language (automatic code
synthesizer) must decide How. Upon what can it base its design?
Some recent work [Mostow & Hayes-Roth, 1979] has proposed a heuristic
approach to operationalizing advice. In this context, what to do is viewed
as the how to do of a higher-level specification. The goal of this work is
to allow a user to specify how to solve a problem at a sufficiently low level
to enable a machine to complete the instruction.
Previous efforts have employed knowledge about program transformations
[Burstall & Darlington][Balzer], programming techniques [Green et al],
task-specific knowledge [Green & Barstow sorting], and
-- if the input language is at all complex -- information to enable
the succesful translation of the input specification into a sufficiently
precise specification of What [Lenat PUP6].
A couple recent efforts have begun to guide the decision-making during code
synthesis by algorithmic analysis [Kant] or even by aesthetics
[Lenat AM][Kevin Kahn IJCAI paper]. But all these methods are
{\it static}: they feed off a fixed base of initially-supplied knowledge,
heuristics, constraints, suggestions, facts. The user supplies a
specification for the desired program, and the knowledge base is employed
to produce that target. The specification may be incremental, and some of
the synthesis may be by dint of synthesizing code fragments, running them,
trapping errors, and then debugging them.
There remains another potentially valuable
source of information:
the history of the program as it is run. The last section sketched ways
in which dynamic program performance could be self-monitored.
This section draws attention to the possibility of applying such usage
data to modifying -- or in the extreme re-synthesizing -- the program.
For example, suppose a hospital
simulation program were specified, and on the basis of
the user specification an event-driven system appeared to be the best design
choice. During subsequent usage, it's observwed that the majority of
questions refer to
precise times of event occurrences. If this had been part of the initial
specification, the design decision would have been made differently, say in
favor of a synchronous time-step simulation. It would be no less useful a
change in the system even at this late date. Even if this redesign is
performed, the environment might keep
changing in various ways, slowly, perhaps even cyclically.
The attractiveness of having a system which could automatically adapt
itself to its current runtime environment is apparent.
The simplest kind of adaptive abilities along this line would be to choose
a data structure, a representation, or an algorithm from a set of well-known
choices
-- and to reserve the right and the ability to change that decision later.
One could gather knowledge about the relative strengths and weaknesses
of each choice, much like the knowledge Kant's system possesses. But this knowledge
could be in the form of rules which ask not only about static data, but which
ask about the runtime environment of the program as well. E.g., ``If
one conjunct appears to be false more often than any other, make it the first
one tested in the conjunction''; ``If each person will use the program only
once, briefly, it is not worth building a model of each such user'';
``A function that is used frequently and changed rarely should be
compiled.''
Yes, such design questions could be answered initially, during program synthesis, but
our suggestion of automating the gathering of such data is a further step
toward the ``What" of artificial intelligence.
There is another possibility, much more exotic than the previous one,
which deserves attention: the discovery -- in ``real time" -- of new
types of data structures and representations which would be useful
for the program in its current environment.
Defining a new data structure is not as difficult as it may first appear:
a data structure can be thought of abstractly in terms of a set of operations
one wants to be able to perform on it (e.g., First, Last, Next, Previous for
lists). The list of desired operations need not be minimal nor concern itself
with which operations are most important, etc. The run-time usage of such
a data structure can be sampled, and that can guide the search for an
ever more appropriate implementation (e.g., in one usage, it might be
very useful for Last to be efficient, and Interlisp's TCONCing might be
chosen as an implementation; in another
environment, it might be useful for Next and Previous to be efficient, and
a doubly-linked implementation would be best).\foo{Dave Barstow is currently
researching issues such as these, at Yale University.}
The two points here are (i) the implementation of a data structure
may depend upon how it is commonly used in a particular spot in a program,
by a particular user, and (ii) a new kind of data structure may be defined
abstractly merely by selecting a set of operations; this choice, too, can
be made by examining the run-time data as it accumulates.
Defining a new representation is not quite so neat. In fact, humans have only
managed to find a handful of representations to date. In lieu of any constructive
suggestions along that line, we shall focus on {\it extending} a given representation.
For a schematized (frame with slots) representation, ``extension" could
occur by defining
new types of slots. The Eurisko program has this capability, and we shall
briefly describe how this mechanism functions.
\SSSEC{Extending a Schematized Representation}
SUMMARY: why is extending a schema. repr. related to efficiency?
what is the hard technical idea?
First, we isolated a few major ways in which new slots are defined from old
ones: {\bf STAR} (e.g., Ancestor $=↓{df}$ Parent$↑*$ which means a Parent of a
Parent of... of a Parent of me; the general case should be aparent);
{\bf UNION} (e.g., Parent $=↓{df}$ Father $\union$ Mother); {\bf COMPOSITION}
(e.g., First-Cousin $=↓{df}$ Child$\circ$Sibling$\circ$Parent; i.e., any
child of any sibling of either of my parents); {\bf DIFFERENCE}
(e.g., Remote-ancestor $=↓{df}$ Ancestor $-$ Parent).
These four operators which define new types of slots
($↑*,\ \union,\ \circ,\ -$) are called {\it slot-combiners}.
Next, we add to AM's knowledge base a concept for each type of slot, and
a concept for each type of slot-combiner. Figure n shows some of the
Generalizations and Star concepts. Note in particular the way in which
Generalizations is defined as Genl$↑*$ -- i.e., immediate generalizations,
{\it their} immediate generalizations, and so on.
[2 concepts]
Finally, we modify the way in which slot entries are accessed.
To illustrate this, we choose a simple task in mathematics, whose paraphrase
is, ``What are all the generalizations of the concept 'premise'?" The
traditional way in which (GET PRIMES GENERALIZATIONS) would work is
to examine the property list of PRIMES, looking for the attribute
GENERALIZATIONS; if found, the entries listed there would be returned.
If, as in Fig. n+1, there is no such attribute, the call upon GET will
return NIL (the empty list).
[network of conepts from primes up]
We modify the way in which any retrieval request of the form (GET C F)
operates. In case the F attribute of
C has no entries (or doesn't exist), we examine the definition of F
and -- if one exists -- try to use it to compute the entries that could
legally be stored on the F attribute of C. More formally, before quitting
we try to (GET F DEFN), and if that succeeds we apply it to C.
Let's continue the example of (GET PRIMES GENERALIZATIONS). As we
see in Fig n+1 above, there are none recorded. So GET now calls itself
recursively; our original call is replaced by
((GET GENERALIZATIONS DEFN) PRIMES).
But as Fig. n shows, there is no slot labelled DEFN on the concept for
GENERALIZATIONS. So we recur one more time. By now our call has become
(((GET DEFN DEFN) GENERALIZATIONS) PRIMES).
Here is part of the DEFN concept:
[Defn concept]
Luckily, it does have a DEFN slot, so we end the recursion.
Applying the entry stored there to the argument ``GENERALIZATIONS,"
we see our original call becoming transformed into
(((GET (GET GENERALIZATIONS SLOT-COMBINER) DEFN)
(GET GENERALIZATIONS BUILT-FROM))
PRIMES)
The slot-combiner of Generalizations is ``Star," and the argument
(old slot) which it is built from is ``Genl." So this turns into
(((GET STAR DEFN) GENL) PRIMES).
We see above that STAR has a Defn entry; it turns the preceding call into
(($\lambda$ (c) (CONS c (self (GET c GENL)))) PRIMES).
This function first calls for (GET PRIMES GENL), which is NUMBERS, then calls
itself on NUMBERS; that in turn calls for (GET NUMBERS GENL), which is
OBJECTS, and calls itself recursively on OBJECTS; that calls for
(GET OBJECTS GENL), which is ANYTHING, and the next recursive call terminates
when it is discovered that ANYTHING has no GENL (no immediate generalization.)
The list CONStructed and returned is thus (PRIMES NUMBERS OBJECTS ANYTHING).
These four items are the legal entries for the GENERALIZATIONS slot of
PRIMES, according to the definition of GENERALIZATIONS.
Notationally there is no distinction between slots which are ``primitive"
(values actually stored as attributes on a property list) and slots which
are ``virtual" (values must be computed using the slot's definition).
A heuristic might refer to the Generalizations of Primes without knowing,
or caring, whether that initiated a single access or a dizzy chase.
To define a new kind of slot, then, one need merely specify one of the
slot-combiners, and list the old pre-existing slots from which it is built.
Thus we might define a new slot, by creating a new concept (calling it,
say, ``DG"), filling its
Slot-combiner slot with the entry ``Difference", filling its
``Built-from" slot with the arguments ``Generalizations Genl." This would
be a new kind of slot, one which returned all generalizations of a concept
except its immediate generalizations; the call (GET PRIMES DG) would return
(PRIMES OBJECTS ANYTHING).
It is only a small extension to see how new
kinds of slot-combiners can be defined. For instance, one which took
two old slotnames as arguments, f and g, and defined a new slot which was
f$↑*\circ$g$\circ$f$↑*$, would be extremely useful (e.g., in database
searches: see [Fiksel & Bower, JMP 1974]). In particular the crucial
slot ``Examples" is defined as Spec$↑*\circ$Immed-Exs$\circ$Spec$↑*$.
Here is another example of how the expanded GET works:
we consider an access on the PARENTS slot, when that slot is not primitive,
but rather is defined as the union of slots for father and mother.
(GET MERLE PARENTS)
((GET PARENTS DEFN) MERLE)
(((GET DEFN DEFN) PARENTS) MERLE)
(($\lambda$ (s) ((GET (GET s SLOT-DEFINER) DEFN) (GET s BUILT-FROM))) PARENTS) MERLE)
(((GET (GET PARENTS SLOT-DEFINER) DEFN) (GET PARENTS BUILT-FROM)) MERLE)
(((GET UNION DEFN) FATHER MOTHER) MERLE)
((($\lambda$ (s1 s2) ($\lambda$ (c) (LIST (GET c s1) (GET c s2)))) FATHER MOTHER) MERLE)
(($\lambda$ (c) (LIST (GET c FATHER) (GET c MOTHER))) MERLE)
(LIST (GET MERLE FATHER) (GET MERLE MOTHER))
(LIST SID BETTY)
(SID BETTY)
\yskip
We have discussed
how a new slot {\it can} be defined; consider now how
a program is to know {\it when/how} to define a new one.
The new type of slot might be defined for purely
exploratory reasons (e.g., it's aesthetic to define ``first cousins'': the
specializations of the generalizations of a concept). The slot's definition
might be based soundly upon need -- or the absence of need. For example,
by monitoring usage, we might
notice that many concepts have a large number of entries for their F slot,
and infer
that the F slot should be specialized. This would lead us to create
several new slots, each having
fewer entries on the average than F had, to cover the original F slot.
In such a case, if we noted that the Examples slot was heavily used,
we might consider creating new slots like Boundary-examples
and Typical-examples. The new kind of slot-combiner
defined in the previous paragraph could be derived from the fact that those
slots which are most useful in the system (e.g., Isas, Examples) share that common
form; or it could be motivated purely from symmetry, and the existing good
uses of it would be noticed only in retrospect.
We close this section with a further exotic possiblity.
If the task domain of the system is the
exploration of (a domain isomorphic to) programming, some new
``theorem" might occasionally be discovered which can be incorporated into a
data structure or
algorithm (or even representation) to speed it up or supplant it.
\NSECP{CACHING: INTELLIGENT REDUNDANCY}
After computing some result, it is typically put to some use, and the result
itself is typically forgotten. If needed again, it is recomputed.
Hardware designers have long recognized (both theoretically [ref] and
empirically [ref Cray?])
the tremendous gain in efficiency affordable by {\it caching}: recording
the result, at least temporarily, in case it is called for again soon.
If that occurs, then no time need be spent recomputing it.
Transferring that notion from hardware to software, and generalizing it
slighty, we have the philosophy we shall call {\it software caching}:
modifying memory to save computed results to speed subsequent accesses.
The simplest case of this is just after computing F(x), for some
function call F with argument x, remember the value that was returned.
Whenever F is called, we first check to see if a cached value is stored
(e.g., associative retrieval on function/argument/value triples; e.g.,
scanning a list of of function/argument pairs for which values are
recorded, or hashing F and x, etc.) If no cached value is found,
F(x) is computed and cached for future usage.
If a cached value is found, then we must decide whether to accept it,
or else to ignore it, recompute it, and store the new value there.
In chess, this might correspond to storing the common openings -- a practice
which uses a great deal of storage, yet is cost-effective {\it because}
the openings frequently recur.
But even this extravagant record-keeping is not complete: we have not saved
information about the {\it process} of computing F(x), the path that was
followed, the traps, the blind
alleys, the overall type of successful approach, etc.
While much more costly to record than simply the value returned by F,
this type of information can often be of extreme usefulness, especially
for the purposes of generalizing, of monitoring the runtime environment
of the program, of leading to new and better algorithms and data structures
(see the preceding section).
The analogue in chess, e.g., was first hinted at by Newell, Shaw, and Simon
in their early chess paper, then elaborated by Berliner
in his thesis [CAPS]: the idea that you should abstract out a
description of a path through the search tree, so
that the remainder of the search could partake of it.
If one path leads to a discovered check against you, so will many others.
You would be wiser to keep that threat in mind, instead of discarding all
your state information and blindly backtracking.
Similarly, in theorem proving, one could store (and perhaps even generalize)
partial proof trees -- and proof finding experiences -- for use in subsequent
proof attempts. In ABSTRIPS [Fikes & Nilsson] we see a program caching partial
plans so it can later reuse them
To illustrate the process of caching values,
consider the way in which (GET PRIMES GENERALIZATIONS) was computed by
Eurisko, as explained in the last section. Several function calls were
required, and a fair amount of cpu time was expended. It would be quite
economical to store the value once computed, to save time in the future.
Eurisko simply stores (PRIMES NUMBERS OBJECTS ANYTHING) as the value of the
GENERALIZATIONS attribute of PRIMES. When the call on GET is reissued, it
tries to access this very spot. Though it failed previously, it now would
succeed, and it would return the cached list almost instantly. No computing
would be done, the concepts of STAR, DEFN, and GENERALIZATIONS needn't be in
core now, and no space (even temporary space) would be required. We might
prefer to enclose cached values within brackets, to indicate their nonprimitive
status.
We saw earlier that notationally (e.g., to a rule) there was no need
to distinguish an access of a primitively-stored slot from an access of a
virtual, computed slot. Now we see that once the value is computed and
cached away, there is no telling it from a primitive one.
Thus, with but a small one-time cost, our program runs as quickly as if
all slots were primitive.
Note that in computing Generalizations of Primes, it was necessary to call for
(GET GENERALIZATIONS DEFN), and the value of this virtual slot was also
computed. The Eurisko policy is to cache this value also. It is useful
because, when a request such as (GET DUCK GENERALIZATIONS) is received, it
would otherwise have to be recomputed all over again. The definitions of
slots are very slowly -- if ever -- changing, hence the recomputation of
Defn of Generalizations is quite a rare event. Caching that value must be
cost-effective in the long run.
In general, we see that caching a value for slot F of concept C is
most applicable when the value can be expected to vary quite infrequently.
In Eurisko, this gives us the flexibility to redefine a slot's definition
if we wish, but (since this will be rare) the program will run just about as
efficiently as if that capability
were absent. This is analogous to compiling: so long as the definition of
a function doesn't change too often, it's undisputedly worthwhile to compile
it. The caching of DEFN and GENERALIZATION slots is not in any way special;
any virtual slot can be cached.
The careful reader may have spotted a difficulty in our caching policy:
what happens if the value {\it does} change? One way to check for this
would be to recompute the value, but of course if this is done too often
it negates the benefits of caching. Eurisko faces this problem by adding
some extra arguments to GET, parameters which describe the
cost/benefit curve
(for each amount of resources expended and each
degree of precision of the result, this curve specifies precisely how
acceptable that resource consumption / accuracy of
solution pair is.) One extreme of this is to provide
an ironclad limit on resources [ref. Boborow's resource-
limited computation], and say ``Do the best you can
within these time/space/... limits." Another extreme
(most common in present-day programs) is to specify
an ironclad goal criterian (``Find an answer which is at
least this good, no matter how long it takes to get.")
We are making the reader aware of the space in between
the two extremes.
To bring us back from the lofty heights of generality, let's see in more
detail how Eurisko does this. First, we linearized this space: we picked a
few significant parameters of it, and defined a description to be merely
a list of values for these parameters.
When a call on GET was executed, and a cached value was encountered, a
formula relating these extra arguments to GET would then determine whether
to accept that cache, or to ignore it and recompute the value.
Eurisko's parameters (extra arguments to GET) are:
cpu time to expend, space to expend, whether the user can be asked about
this, how fresh the cache must be, minimum amount of resources which must have
been expended at the time the cache was written.
So (GET PRIMES GENERALIZATIONS 200 40 NIL 3 0) would allow any cached
value to be accepted if it appeared that recomputing would take more than
200 milliseconds, or would use up more than 40 list cells, or if the value
had been put there less than three Cycles ago (in Eurisko, a Cycle is the
time it takes to work on the top-rated task on the top-rated agenda).
Otherwise, the cache would be ignored, a newer value would be computed, and
it would be stored away. With it would also be recorded
(i) the information that it was
a cached value, not a primitive one, (ii) how long it took to compute,
(iii) how many list cells it used up in computing this value, (iv) the current
Cycle (number of tasks worked on so far). The above call on GET might result
in this value being stored on the GENERALIZATIONS slot of PRIMES:
(*cache* (PRIMES NUMBERS OBJECTS ANYTHING) 54 6 9).
[[ Contrast with psychological conjectures of cognitive economy
(e.g., Collins&Quillian, KRL, ...). More like $HR↑2$ Plasticity
model of storing all retrieved paths as direct links
]]
[[I can gues what this means, namely the horse isa animal being
better than horse isa mammal, but you (Rick?) should do this section.]]
[[Mention the psych. studies that show that people do develop direct association
between words that are co-retrieved often. Thus dog and animal are closer
than dog and mammal, even tho dog-->mammal--->animal in the hierarchy.]]
[[Also: the stuff about people reasoning in terms of
words themselves,rather than primitives, since the ``high level code" (words)
is more efficient.]]
The caching process involves storage and updating. For both of
these aspects, we can discuss details of when, why, how, and what.
The decisions that arise are made with the guidance of heuristic rules,
and below we present many of those heuristics. We have omitted many of the
very general ``common-sense" heuristics, and those which deal with details
of Lisp programming. We also have specified the rules in Enlgish, rather than
in Lisp; we have freely used expressions like ``recently", although in any
encoding that would have to be made much more precise.
Besides storing and updating, a common decision to be made is whether to
accept a cache or not; this has been discussed above and will not be duplicated
in the heuristics below.
Finally, note that these heuristics are not {\it always} relevant; they are
applicable for many AI programs, running on PDP-10-sized computers, running
Interlisp, with a human user watching and interacting.
There would be other rules for other machine architectures and languages.
In other words, one could say that we have only partially specified the
IF-part (left hand sides) of the following heuristic rules. An alternative
would be to build up an entire knowledge base of heuristics just to determine
the applicability, the domains of relevance,
of the following (as a function of machine and language.)
[[the following will be in 3 boxes or figures]]
STORAGE PRINCIPLES
------------------
When (and when {\it not} to)
Every time you have to call a lower order function.
You called a function and it took a long time to return.
The value returned has not changed since the last time you called it.
The amount of time to recompute the value would be very high.
E.g., after a lucky accident, where a repeat might
be very costly or even fail entirely to duplicate
your recent success at getting a solution.
If (freq of usage)x(avg cost to recompute)/(freq of change)
is high, then it pays off.
If the value is so critical that the cost-benefit criteria
(eg the resource limits are enormous) always favor
recomputation rather than chancing a blunder,
Then don't cache.
If the function evaluates as fast as the caching mechanism itself,
or if space is too tight, don't cache.
F is called with the same argument x very often.
Why
Temporal cost of recomputing is higher than spatial cost of storage.
Related to ``When" rules above; namely: in those situations, it's
cost-effective to store a cache.
Analogy to utility of hardware caching.
Ability to utilize cached values as usage data to induct upon.
Where
The value to be cached should have a precise storage place.
One extreme is an assertional database, with {\it no} structure.
We prefer to add slot and subslot structuring, with some
domain-specific tinkering of those two sets (especially
the former, the set of slots.)
Thus an extreme example of prime numbers should be stored
on a slot called extreme-examples, on a schema called primes.
At access time, we look in the precise spot(s) where X would
be, and if it isn't there, we compute and cache it right there.
At worst, there should be a precise {\it set} of places where X
might be, a well-defined path to search down for X (e.g.,
a conjecture about prime numbers would either be an Example of
Conjectures, or a Conjecture of Primes; if not in either of those
places.)
How
Before (re)computing F(x), the program presumably searched in the
``right place'' (see ``Where'' above) to find a cache of
F(x) if one existed. At that time, set a pointer to that
place, and when the value is found, place it there.
Called functions might suggest how to cache their value in higher
calling caches
E.g., ``my value changes often so compile my definition
and cache that, but don't waste resources caching this value.''
Cache should be transparent and discardable (should be able to throw
them all away if space is needed).
If there are multiple places to store it (e.g., you learn that
X is a PARENT of Y, but PARENT is a virtual slot defined as
MOTHER $/union$ FATHER; if the cache is to be discardable, then
we must store X under either Y's MOTHER or FATHER slots.)
Then here are some strategies one might use:
Store it redundantly in several (all possible) places
Pick one of the places at random and store it there
Look up information about each place, to decide
Pick one of the places accurately by reasoning, testing, etc.
What
Store the returned value in any case.
Good policy to store a description of the {\it call} which led to
this value being computed. E.g., make sure you
store the amount of resources allotted, the
time of day and the relative place
in the computation (e.g., task number), whether
the user was allowed to be queried, etc.
Along with the call, store data about the actual path to a solution.
This includes algorithms used, time it took to compute,
which other caches were used, etc.
It may be useful to store other intermediate results of the process
that led to the value's being computed successfully
(e.g., a trap that was found and may crop up again.)
This also includes storing some abstract, partially-evaluated
symbolic expressions which generalize the value and its
computation.
If possible, predict (criteria, time-limit, etc.) conditions under
which this will no longer be current. E.g., ``Depends
on the definition of Y being known, and on there being
no examples of Z known, and...'')
Include a discussion of the certainty of the result.
It may be worthwhile to {\it stack} the previous cached values,
enabling the program to determine if (when, how, how often)
they're changing.
If you choose not to cache, you may wish to store a marker recording
-- and hopefully explaining -- that decision.
How to eliminate caches
Just reverse the criteria in ``When" (above), to see if it
is no longer cost-effective to keep the cache.
Remember that F(x) will occupy varying amounts of space,
varying with F, x, and time.
AM, e.g., eliminated largest cached values first.
Eliminate least frequently (or least recently) used caches first.
In general, eliminate the caches that are least cost-effective.
UPDATING PRINCIPLES
-------------------
When
If the current request would have produced a different answer.
Usually, only do this if the current request will produce a
distinctly {\it better} answer. For instance:
If the current request specifies more precision in the answer.
If the resource allocation is high enough to get a better
or more current answer than the one cached already.
Trivially: If there is no cached answer available.
Typically: x or the definition of F changed since F(x) was cached.
Why
Frame problem: if the value is old, it's hard to know for sure that
the world hasn't changed since it was computed.
If new value is computed (either intentionlly or accidentally),
and its freshness (or the other conditions of its call)
makes it ``better" than the existing cached value.
How
Discard the old value, or remember it elsewhere (maybe on disk).
Can use demon traps that flag the cache as out of date, without
bothering to recompute the value if not required to.
If the new value is found, simply store it.
The user may want to know about the updating.
Many other cached values may depend upon this one, and they may have
to be ferreted out and updated also, or at least some
information should be left posted so they can later determine
that they may be out of date.
Usually: discard the whole old value, store just the new one.
If the program is very smart: When the world changes, try to
propogate that change through the network of caches,
changing {\it them}. This is much better than erasing them!
Caching, as we have described it, is merely the lowest-level of a tier of
data reduction processes, techniques for compiling hindsight into usable,
{\it more efficient}, more procedural forms.
To see this, consider the progression of ever more sophisticated tasks
which programs perform [see Fig. n]: accessing a datum, calculating a
value from a fast algorithm, deducing a result by searching for a solution
or proof in a well-defined space,
inducing a result by a very open-ended search process.
Often there is the opportunity to take experiences at one of these levels of
sophistication and abstract them into an entity which is one level lower,
yet which appears to contain almost the same power.
Consider first the way in which we reduce induction. After
much experience with inducing, we produce a {\it heuristic rule} which
enables the same inferencing to be done in a much more controlled space,
in a much more deductive way. Heuristics reduce discovery tasks to mere
(!) symbolic manipulation within a well-defined system (as in AM).
Deduction is reduced similarly. By many painful deductions, we gain knowledge
of the space we are searching, e.g. by deriving many theorems about it.
Those theorems can then be used to vastly simplify our search. Ultimately,
the process becomes efficient calculation. A short, optimal algorithm may
be found, e.g., which replaces a search for a solution (this has recently
occurred with the ``n queens'' chess problem.)
Now we see that our caching process is the next step in this progression.
It reduces a calculation (e.g., to traverse a particular access path to
gather all Ancestors of a node) by a lookup, by a single access of a datum
in memory.
[[here is that fig]]
ACCESS==> CALCULATE ==> DEDUCE ==> INDUCE BY OPEN=ENDED SEARCH
\ / \ / \ /
cache thm, alg heur rule
[[note: saving multiple
instantiations of the same rule at different levels of abstraction is
NOT worth mentioning, I think, since it is a STATIC (eg planning) tactic;
I may be wrong, and perhaps we should at least mention this v. briefly anyway]]
[[Should we metnion explcitly the loss that may occur if the task involves
a lot of reasoning one's
way through delicate inference chains efficiently; or: a lot of
synthetic reasoning or rule interaction?]]
\NSECP{EXPECTATION-SIMPLIFIED PROCESSING: INTELLIGENT FOCUS OF ATTENTION}
Central notion: reserve your computing for opportunities to realize
potential for expanding knowledge
Ie: be willing and able to add new facts,
but be eager to add surprising new facts.
Equivalently: by being guided by expectations (albeit from
stereotypes) of situations (frames), events (scripts),
and of people (user models),
you will find yourself zipping through 90% of what
comes in from he world, and spending most of your
processing time on the remaining puzzles, anomalies.
Some slots will have meta-comments like ``I'm worth computing
or verifying'', or just the opposite (e.g., in our
Room frame, we have a default Ceiling, but we know not
to squander time checking that each room we're in has
a ceiling. Similarly for emergency exit signs: we have
in both sittuations a very fast algorithm we can apply
if ever we are in a situation to want that information.
For cieling, it's look up; for exit signs, it's look for
red on white lettering, and in a sudden power outage
we expect those signs to be one of the few things we
could still see.
You may decide how much to expend re-confirming the expected
You may decide how much time to spend deciding how much time..
Reductions realizable through expectations:
Perceptual set: see what you expect with less effort
For exit signs: when needed, look for horiz. and
vertical red lines; this is 99% effective.
Surprise: heighten sensitivity to data inconsistent with
expectations
Perhaps mention analogy to frog's visual system.
Frames dull our chance of noticing a surprising datum
(since we will tend to interpret any data as consistent
with the current frame) but, when a surprise IS noticed,
it has quite a significant impact.
Notice that surprises can (almost tautologously) exist
only in the context of expectations.
Defer
Often a perception will be easier to make when it is
needed; e.g., the lit red exit sign in a dark theater.
In general then it's worth a little computing to reason
out whether (and maybe even how long) a slot-filling
can be ignored.
Predict and prepare
This includes a whole continuum, growing more
flexible, more descriptive (less scalar), dynamic:
> Store a value, by binding a variable to it, so you can
later refer to it (retrieve it) by name.
> Cache the value of a function-call, so if you ever want
to find F(x), first you look to see if that value is
already computed and stored away, else you compute it.
Note that this is much like hashing, like associative
memory: the idea that you have a place where F(x)
should be (the hash of the string PARENTS(FRED), eg)
and you look there first. This is just a genl. of
the previous ``>" about binding a variable to a value.
> After finding F(x), store the information that would
enable you to recompute it rapidly. Hopefully, this
will also help you compute F(y) (either for all y
or at least for some y's similar to x), and possibly
will even help you compute G(x), where G is similar
to F (and, much more rarely, G(y)).
The idea here is to cache an algorithm, or at least
constraints on a search, for finding F(x).
One very special case of this is normal compiling:
the compiled code for F is just a more efficient way
of finding values of F. As with our above remarks, one
often finds his code worked interpreted but not
compiled. This is considered ``wrong" (ie a bug in the
compiler), but is much more in line with our general
idea of mere assistance, which is sometimes quite
useful but may sometimes not help you at all.
> Synthesize and store away a partial mode of the world.
This may include a (sbu)network of frames, which
together capture enough about the situation that
in the future its relevance will be recognized, and
some aspects of this situation will help guide future
processing on some problem (which is recognized as
similar). This is much like analogy, like real
"learning" (storing away experiences).
Note the two purposes here: recognizing the need to do a sim.
computation, and speeding/eliminating it when recognized.
Much of what goes on today at the fore of AI can be viewed as
"expectation-simplified processing": frames, scripts, user modelling,
caching of all levels and flavors,... Here are a few poins on the
continuum:
After computing a value, cache it. Note: ``value" may be a number,
a vector of numbers, an alphanumeric identifier, a vector of them...
Synthesize a function capable of efficiently computing desired values,
and cache that function.
Synthesize a whole concept data structure (frame, script...) which
contains relevant partial models of the recent situation.
There are more intermediate ones, but you see the progression from
static to dynamic, from scalar to descriptive. In all cases, the
motivation for doing this storage is (i) speed up the recognition of
(the need to do) similar computations in the future, and (ii) speed up
or even eliminate those computations when you decide they ARE relevant
and you want the values they would return. These are the two uses of
scripts, but also of cached constants (e.g., caching the value returned
by OWNED-BY, a function from CARS to PEOPLE). A better example: user models,
as they range from a single number, to a few numbers (e.g., in PARRY),
to a dynamic concept-modelling scheme.
What mechanisms are implicated?
Caching
This should encompass also normal Compiling of subroutines.
PDMs (as triggers or demons)
The analogy: you hear someone yell ``Fire!" in a theater.
Also: mention the basis for much of humor: the punchline.
The intentional misleading initially (wrong LHS)
An unexpected reaction (wrong RHS)
This may even provide a start at a taxonomy of
humor, one which coud be operationalized.
Relevance to this paper:
Programs should build up expectations, monitor them,
and change their models as needed.
Confirm or disconfirm predictors
This requires setting up PDMs to fire on dis/confirmation
Yes, the idea is that when an expectation is not met, we
also (have some chance of) modifying the culprit
rule(s) that made that false prediction (and/or
adding new rule(s) which would make the right one.
THis is v. similar to Mycin's task, and the TEIR.
approach is worth mentioning.
This ties learning in very closely to scientific theory
formation (at least the theories of knowledge which
are activist, revolutionary conventionalist activist,
methodological falsificationist, sophisticated.
[those are the nodes descending in a genl/spec hier
of theories of knowledge]
\NSECP{LEVELS OF ABSTRACTION: INTELLIGENT KNOWLEDGE STRUCTURING}
In many real-life problem solving situations, the ``goal" is not a single,
precise answer. Rather, there is a cost-benefit tradeoff between the
accuracy of the solution and the amount of resources consumed in producing
it. As with any such tradeoff, there is typically a point of diminishing
returns. Computer programs which are designed only to return exact answers
will then be ill-suited to the needs of the various situations in which they
will be called upon. One area in which this is recognized in AI is game-
playing. The concept of truncated search is fundamental in all chess programs
Yet very little of the same philosophy has permeated to other kinds of
AI programs, let alone programs in other spheres.
[this last para. needs reworking; my analogy to truncated search may confuse
more than illuminate.]
[Even in chess research, very little abstraction -- intensionality -- enters
into search and evaluation. Most plans are concrete, and relate to
low-level board descriptions.]
As we discussed in Section 2.1, one of our fundamental assumptions is
that the environment is continuous. This justifies the belief that
a truncated search is better than random selection of a legal move. We assume
-- or must work to assure -- that our abstractions are approximations to the
next level of detail, which in turn approximates the next more detailed level,
etc. (perhaps all the way down to the ``real world," to the true leaves of the search
tree). An apparent exception is the situation of a rapidly changing
environment. But if the world keeps changing, then that character of it is
remaining more or less constant, and the program might hope to tailor itself
into a form that was especially good at rapidly adapting, even if it were
quite slow for any given fixed environment. In fact, such an adaptable
program would share much in common with what we've termed ``expressive"
programs.\foo{ An instance of this of particular interest to us is biological
evolution: The physical world, and ecosphere, have always been rapidly
changing. It makes sense, then, to expect that advanced organisms would
have evolved good methods for quick adaptation; e.g., their progeny would
vary because of some expressive ``plausible mutation" mechanism, rather than by
some efficient streamlined one, or (even less likely) by the purely random
generation of mutation mechanism which underlies Darwinism and neodarwinism.
``Mutation" here encompasses low-level sequence mutations, high-level
recombination, gene duplication, sexual combination, etc.
One should not attempt to take on an entire established paradigm in a
footnote, so further discussion of evolution by plausible mutation will be
deferred to a later paper.}
Let's look at a couple examples illustrating the omnipresent need to
approximate reality -- a need which is well met by maintaining multiple
representations of the world at various levels of abstraction;
i.e., an entry in the knowledge base has all its generalizations also
stored explicitly, redundantly.
A train accident occurs, and over two hundred people are injured; the
only large nearby hospital is called, and asked if they can handle the load.
The administrator queries his shiny new hospital operation simulator,
and it begins to chug
away. It looks over the state of each current patient, each physician,
each hospital resource. It begins simulating the arrival of the wounded,
their movement and temporary storage in hallways, etc. After quite a while,
it shows that the hospital will be saturated and unable to care for any more
incoming patients. The maximimum they can accept is 157 wounded passengers.
If ``quite a while" is several hours (which it very likely would be),
this type of anaysis is
simply inappropriate. There is a pressing need for a rough answer quickly;
a {\it human} hospital administrator would answer right away, or after a
very brief survey of a few parameters, and {\it so should
an intelligent program}.
A colonel monitoring our defense systems detects a fleet of enemy aircraft
attacking in an unexpected pattern. Can our bombers and missiles meet this
new attack mode? The colonel will know precisely how much time is available
to answer that question, and it will be a matter of seconds or minutes, not
of hours or weeks. A detailed simulation program will be of no use to him.
Reasoning will go on at a high-level of abstraction, and an approximate answer
will be forthcoming (either from a program capable of such inference, or
-- in lieu of that -- the colonel's head).
[what are some other possible examples to use here? We should pick say two,
and use the same ones throughout the paper, whenever possible.]
In addition to aiding us in quickly approximating reality, multiple levels
of abstraction (``MLA") are useful for
{\it analogizing}: they can
make that process easier, faster, and occasioanlly even
more valid. Analogies can be recognized when two distinct concepts turn into
the very same abstraction at some level. Conversely, if two apparently related
concepts (such as two homonyms) do not share related structure at higher
levels of abstraction, that suggests that an analogy between them would be
superficial and lacking in power. Even more strongly, consider the situation
where a general model of page usage exists for some operating system, and
at the next lower level are
four mutually inconsistent, specialized, detailed models. It may
be that no one of the detailed models can provide results as good, on
the average, as the general model, which is thus more valid.
In several ways, we have seen how MLA can be an instrument of efficiency.
But this is very strange: we earlier said that reasoning at multiple levels of
abstraction was a technique for heightening expressiveness, not efficiency:
MLA facilitates precision in reasoning through delicate inference chains; the
presence of highly general rules facilitates rule interaction.
We have spent most of this paper discussing dynamic methods for approximating
reality (e.g., the cached value for Generalizations of Primes may suffice if
a rough answer is needed quickly). Although the technique of reasoning at
multiple levels of abstraction is much more ``static'', its usage in AI programs
to date has been primarily for expressiveness, not for efficiency. We wish to
clarify how it serves both apparently conflicting goals.
Is this such a powerful ability that it helps improve both simultaneously,
or is something else going on? The answer lies, significantly, in the
nature of the task environment.
Multiple levels of abstraction cost a certain
amount to implement, both initially (man-hours of programming) and as the
program runs (cpu time spent maintaining the redundancy, choosing which level
to work on next, etc.) For problems of all sizes, this feature aids in the
expression of new problems to the program, since they may be input at whatever
level(s) seem appropriate to the user. Thus multiple levels of abstraction
will always add to expressiveness, and will either detract or add to
efficiency depending upon how small or large the task is. And as we showed in
a recent paragraph, MLA is very useful when the program's resources are
curtailed or, even better, varied dramatically in magnitude from run to run
(a program which was {\it always} limited to a 15-second execution time would
be designed specifically for that task, but a program which might get anywhere
from 5 seconds to 5 hours for the same simulation question could better
benefit from multiple levels of abstraction.)
The graph below summarizes these two results: it pictures MLA
contributing more to efficiency
as the quotient (task size)/(resource allotment) increases in size.
[[space for graph]]
\yskip 3in
There is a more general result here: the methods which humans find useful for
easy expression of problems may be useful to programs attacking very large
problems. For instance, consider the decision about whether to do inference
by a system of pattern-invoked experts, or rather to preprocess the triggering
conditions into a big discrimination network. The former approach is more
expressive, the latter more efficient -- at least for small problems. For
very large tasks, the need to remain flexible grows very large. It is then
more economical to retain pattern-directed control (the compilation of the
patterns is so complex the whole procedure would have to be redone
frequently during the course of execution, if we opted for that alternative
instead.) A case in point is the HARPY speech understanding program
[Lowerre & Reddy ref]:
whenever the grammar changes -- at any level -- the entire speech recognition
network must be recompiled. HEARSAY II [Erman & Lesser IJCAI 77],
while slower in performance, has
sufficient flexibility (from several independent pattern-directed knowledge
sources) to obviate such monolithic integrative recompilation delays.
[[Is any of the following appropriate for inclusion, either in this section
or anywhere else in the paper? It could be used to build a full explanation
of MLA, which we simply assume readers grok completely.]]
[[MLA is equiv. to Genl/spec hiers.. MLA ties in to efficiency.... include here
inheritability (ark!!)]]
Conceptual hierarchies
Hier. in general: possible organizing relations
Supervises, commands, controls, calls (as in subroutin
Containment: part-of versus specialization-of versus
application-of versus element-of
Inheritability: the importance of ``or any ancestor"
The notion that the hier. is a compact way of storing
a huge set of assertions, is fairly efficient
vis a vis retrieving / testing for them, and
is much much more efficient for updating them.
This discussion should be general to all above
organizing relns, not just genl/spec hiers.
Make sure to distinguish our meaning for abstraction
(redundant, generalized version) from the other
common meaning (inducing a general case from examples)
Heuristic Hierarchies
Each heuristic H has a domain of relevance
More precisely, H's relevance is a function of task posed,
and is high for some (it domain of relevance),
low for many more, and perhaps negative for others.
Heurisitcs can be related to each other by genl/specialization
[example: ``If P(x) is often false, weaken P" -->...
Also an example involving simulation.]
Heuristics can be object-centered (tacked onto relevant
concepts) and can therefore inherit THEIR relationship
[an ex. of that.. This is ``Inheritability" in AM
sense.]
Interpretation and planning at levels of abstraction
Eg., rules of bomber simulation at difft levels
(this example can be one which is used earlier to suggest
caching for simplification)
[this ties in with the last point about heur. hier.]
Part of this para. might be this example:
``In the short run, what would happen if we didn't take any defensive
actions in a full-scale enemy attack situation?" A strategist can
answer this instantly, to the effect that the enemy missles and bombs
would then reach their targets, destruction would be nearly total, our
capacity for retaliation would be severely reduced, and so on. He can
say this without factoring in the individual changes in aileron
attitutde throughout the flight of each bomber.
He has a high-level ``script" which specifies defensive action against an
attack, with a small note of explanation (e.g., ``else destruction"), and
that's as detailed as he needs to get to answer the question.
Now consider a question like ``What if we had a fleet of 200 B1 bombers
in addition to our current forces?" The strategist may again be capable
of giving a quick estimate of the effect, but it's possible that a more
detailed analysis would reveal some cusp, some nonlinearity not apparent
to him through simple extrapolation, through the application of general,
high-level rules of thumb. One strategy might be to employ his old, general,
high-level scenario as a plan, as a set of general expectations
which guide the detailed simulator, which predict which aspects of the
world will benefit from much more detailed simulation (e.g., encounters where
our bombers hitherto failed to reach their targets), and which areas will
probably be unaffected by the change in the world (e.g., attacks on our
coast by enemy submarines, attackes which succeeded before).
[note that we can easily extend this discussion a bit for caching: keep
around the old simulation, at various levels, and only re-run those parts
which might be affected by the change in initial situation, and even then
only rerun it at the hihest level possible. This latter decision is probably
always made locally: run until the results stop changing, then you know
you've expanded down one level too far, so you can back up and stop.]
Related research
Include mention of psych. studies showing that people may
reason at the word level, rather than more primitive
level, because the high-level word manipulation
process is more efficient than the manipulation of
large, detailed structures (such as huge sem. nets).
\NSECP{COGNITIVE ECONOMY REVISITED}
[let's leave this section until last, till the others are written out]
Sample problem: using a world model (simulator) to answer questions
(e.g., what'd happen if 100 bombers went in there?)
Representation of this knowledge as PDMs at difft levels of abstn
Ability to generalize and cache results at one level at the
next higher level,
e.g. either as numerical tables, stat. distns, or
symbolic expressions
Ability to answer some questions appropriately for the requestor
at a high level of abstraction
KB Design
One good reason to use inheritanc is to speed knowledge
implementation, not computing performance
Using the system should result in its speedup
Storage should be cheap
Machine architecture
PDI should be cheap
PDMs should be scheduled with variable resources and
should be able to spend effort accordingly
How could propagation of changes be made efficient?
\NNSECP{Acknowledgements}
We wish to thank...
\vfill\end